package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：1.9 MB, 在所有 Go 提交中击败了65.85%的用户
 */
var n int
var col, dg, udg []bool

func totalNQueens(_n int) int {

	n = _n
	col = make([]bool, n)
	dg = make([]bool, n * 2 - 1)
	udg = make([]bool, n * 2 - 1)

	return dfs(0)
}

func dfs(u int) int {

	if u == n { return 1 }

	res := 0
	for i := 0; i < n; i++ {
		if !col[i] && !dg[u - i + n - 1] && !udg[u + i] {
			col[i], dg[u - i + n - 1], udg[u + i] = true, true, true
			res += dfs(u + 1)
			col[i], dg[u - i + n - 1], udg[u + i] = false, false, false
		}
	}
	return res
}

func main() {

	fmt.Println(totalNQueens(4))  // 2
}
